\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage{fancyhdr}
\usepackage{amsfonts}
\pagestyle{fancy}
% wstawianie obrazkow
\usepackage{graphicx}
\usepackage{subfig}

\begin{document}
\title{Równoważenie obciążenia w sieci robotów internetowych} % może być taki tytuł?
\author{Adam Grycner, nr indeksu 209179
	\and Łukasz Kornek, nr indeksu 209145}

\begin{titlepage}
\maketitle
\thispagestyle{empty}
\end{titlepage}

\tableofcontents
\newpage

\section{Opis problemu}
Należy zarządzać siecią agentowych robotów internetowych (ang. \textit{web crawlers}), tak aby:
\begin{itemize}
\item agenci nie odwiedzali tych samych stron wielokrotnie,
\item agenci dzielili się pracą,
\item było możliwe dodawanie i usuwanie agentów z sieci w czasie pracy.
\end{itemize}

\subsection{Obliczanie obciążenia}
Aby dobrze opisać, jak agenci powinni dzielić się pracą, należy zdecydować się na sposób obliczania obciążenia agenta. Zastosowany sposób:
\[
L_a = qsize(a) / avg\_upt(a)
\]
gdzie:\\
$L_a$ - obciążenie agenta $a$,\\
$qsize(a)$ - rozmiar kolejki adresów stron do odwiedzenia przez agenta $a$,\\
$avg\_upt(a)$ - średnia liczba stron odwiedzanych przez agenta $a$ w określonym czasie.


\section{Rozdzielanie zadań}

\subsection{Consistent hashing}
Każdy agent posiada strukturę, która informuje go komu należy przydzielić dane zadanie. O strukturze możemy myśleć, jako o okręgu, na który będziemy mapować ,,hasze'' agentów oraz ,,hasze'' adresów url. Każdy agent, ma przydzielone kilka punktów na okręgu. Strona o ,,haszu'' $h$ jest przydzielana agentowi o najmniejszym ,,haszu'' większym niż $h$. Graficzną prezentację metody widać na rysunku~\ref{F:const}. Dzięki \textit{consistent hashing} gwarantowaliśmy sobie, że agenci nie będą wykonywać nadmiarowej pracy. Każdy adres url jest przydzielony dokładnie jednemu agentowi i to on decyduje, czy zlecić komuś wykonanie zadania (pobranie zawartości adresu url).

  \begin{figure}[ht]
    \begin{center}
	\includegraphics[width=0.4\textheight]{obrazki/cons.png}
    \end{center}
    \caption{Consistent hashing}
        \label{F:const}
  \end{figure} 

\section{Zastosowane metody równoważenia obciążenia (ang. \textit{load balancing})}
W programie zastosowane zostały następujące metody równoważenia obciążenia:

\subsection{Sender initiated load balancing}
Agent pyta innych agentów o ich obciążenie. Jeśli jest przeciążony (istnieje agent, który jest mniej obciążony), wysyła do najmniej obciążonego agenta taką liczbę adresów, by ich obciążenie było równe.

\subsection{Random load balancing}
Agent pyta losowego agenta o jego obciążenie. Bardziej obciążony z nich wysyła mniej obciążonemu taką liczbę adresów, by ich obciążenie było równe.

\subsection{Centralized load balancing}
Wybrany w sposób zdecentralizowany agent pyta innych agentów o ich obciążenie. Następnie wydaje agentom polecenia przesyłu pewnej liczby adresów innym agentom.

\section{Testy}
W naszych testach porównaliśmy trzy metody równoważenia obciążenia (\textit{sender initiated load balancing}, \textit{random load balancing}, \textit{centralized load balancing}). Poza tym każdy agent stosował \textit{consistent hashing} do ustalania, czy dany adres url został już sprawdzony. Dodatkowo sprawdziliśmy, jak równoważą obciążenie agenci używający tylko \textit{consistent hashing}.
Na rysunkach mamy przedstawione wykresy obciążenia czterech agentów na przestrzeni godziny.

\subsection{Sender initiated load balancing}
  \begin{figure}[h!t]
    \begin{center}
	\includegraphics[width=0.6\textheight]{obrazki/plot_senderLB.png}
    \end{center}
    \caption{Wykres obciążenia na przestrzeni godziny przy \textit{sender initiated load balancing}}
        \label{T:send}
  \end{figure} 
\begin{itemize}
 \item Średnie odchylenie standardowe: 352
 \item Średnia różnica między największym a najmniejszym obciążeniem: 888
 \item Liczba wysłanych wiadomości: 6960
 \item Liczba odebranych wiadomości: 9871
\end{itemize}

\subsection{Random load balancing}
  \begin{figure}[h!t]
    \begin{center}
	\includegraphics[width=0.6\textheight]{obrazki/plot_randomLB.png}
    \end{center}
    \caption{Wykres obciążenia na przestrzeni godziny przy \textit{random load balancing}}
        \label{T:rand}
  \end{figure} 
\begin{itemize}
 \item Średnie odchylenie standardowe: 269
 \item Średnia różnica między największym a najmniejszym obciążeniem: 679
 \item Liczba wysłanych wiadomości: 3539
 \item Liczba odebranych wiadomości: 3495
\end{itemize}

\subsection{Centralized load balancing}
  \begin{figure}[h!t]
    \begin{center}
	\includegraphics[width=0.6\textheight]{obrazki/plot_centralLB.png}
    \end{center}
    \caption{Wykres obciążenia na przestrzeni godziny przy \textit{centralized load balancing}}
        \label{T:central}
  \end{figure}
\begin{itemize}
 \item Średnie odchylenie standardowe: 472
 \item Średnia różnica między największym a najmniejszym obciążeniem: 1206
 \item Liczba wysłanych wiadomości: 3006
 \item Liczba odebranych wiadomości: 3756
\end{itemize}

\subsection{Consistent hashing}
  \begin{figure}[h!t]
    \begin{center}
	\includegraphics[width=0.6\textheight]{obrazki/plot_cons_hash_5_load.png}
    \end{center}
    \caption{Wykres obciążenia na przestrzeni godziny przy \textit{consistent hashing}}
        \label{T:cons_load}
  \end{figure}
\begin{itemize}
 \item Średnie odchylenie standardowe: 2106
 \item Średnia różnica między największym a najmniejszym obciążeniem: 5377
\end{itemize}
Jak widać samo \textit{consistent hashing} nie równoważy dobrze obciążenia. Ponieważ jednak działanie \textit{consistent hashing} nie zależy od obciążenia agenta, na drugim wykresie przedstawiamy zmianę wielkości kolejki agentów w czasie. Innymi słowy, jest to wykres działania agentów przy założeniu, że przeglądają adresy z taką samą szybkością.
  \begin{figure}[h!t]
    \begin{center}
	\includegraphics[width=0.6\textheight]{obrazki/plot_cons_hash_50.png}
    \end{center}
    \caption{Wykres wielkości kolejki na przestrzeni godziny przy \textit{consistent hashing}}
        \label{T:cons_size}
  \end{figure}


\section{Wnioski}
Zastosowanie \textit{consistent hashing} zapewnia, że adresy url będą sprawdzane tylko raz. \textit{Consistent hashing} dość dobrze rozdziela adresy pomiędzy agentów o równej przepustowości łącza. Można dostosować je też do agentów, którzy mają różną przepustowość łącza, odpowiednio ustalając ilość punktów przyporządkowanych agentom. Ma jednak poważne ograniczenia. Jest to bardzo sztywne rozwiązanie - jeśli w trakcie działania agenta zostanie ograniczona jego przepustowość, \textit{consistent hashing} nie zrobi nic, by przenieść część jego pracy na innych agentów (rysunek~\ref{T:cons_load}). Ponadto równomierne rozdzielanie adresów zależy od dobrego wylosowania punktów agentów na okręgu, co nie zawsze się uda.\\
Dlatego konieczne jest użycie dodatkowej metody równoważenia obciążenia. Dla niewielkiej liczby agentów najlepszym rozwiązaniem wydaje się \textit{random load balancing}, które w testach uzyskało najmniejsze różnice w obciążeniu. Jednak wraz ze wzrostem liczby agentów prawdopodobnie inne metody będą działały lepiej niż \textit{random load balancing}, ponieważ kontaktują się w większą liczbą agentów w celu równoważenia obciążenia.\\
Z pozostałych dwóch przetestowanych metod \textit{sender initiated load balancing} daje mniejsze różnice w obciążeniu agentów, ale wymienia o wiele więcej komunikatów między agentami niż \textit{centralized load balancing}. Wadą \textit{Centralized load balancing} jest centralizacja procesu wymiany adresów, co może prowadzić do przeciążenia centralnego agenta.

\section{Obsługa programu}
\subsection{Wymagania}
\begin{itemize}
\item Python 2.6.x (http://python.org/)
\item biblioteka spade (http://code.google.com/p/spade2/)
\item biblioteka BeautifulSoup (http://www.crummy.com/software/BeautifulSoup/)
\end{itemize}
Instalacja bibliotek Pythona:
\begin{verbatim}python setup.py install\end{verbatim}

\subsection{Uruchamianie agentów}
\subsubsection{Uruchomienie platformy}
\begin{enumerate}
\item \begin{verbatim}spade/configure.py server_ip\end{verbatim}
\item \begin{verbatim}spade/runspade.py\end{verbatim}
\end{enumerate}
gdzie:\\
\textbf{server\_ip} - adres IP platformy spade
\subsubsection{Uruchomienie agenta-robota}
\begin{verbatim}sia-crawling/main.py agent_name server_ip LB_type
[number_of_threads=1 seed_urls_file=None]\end{verbatim}
gdzie:\\
\textbf{agent\_name} - nazwa agenta\\
\textbf{server\_ip} - adres IP platformy spade\\
\textbf{LB\_type} - rodzaj równoważenia obciążenia:\\
1 - sender initiated LB\\
2 - random LB\\
3 - centralized LB\\
4 - tylko consistent hashing\\
\textbf{number\_of\_threads} - ilość wątków przeglądających strony\\
\textbf{seed\_urls\_file} - plik z początkowym zbiorem adresów1
\subsubsection{Uruchomienie agenta-statystyka}
\begin{verbatim}sia-crawling/StatisticsAgent.py agent_name server_ip\end{verbatim}
gdzie:\\
\textbf{agent\_name} - nazwa agenta\\
\textbf{server\_ip} - adres IP platformy spade
\end{document}
